home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / umich / falcon / programm.ing / nt_dsp1.lzh / NT_DSP1.MSA / SORT / SORT2.ASM < prev    next >
Assembly Source File  |  1989-01-24  |  2KB  |  75 lines
  1. ;
  2. ; This program originally available on the Motorola DSP bulletin board.
  3. ; It is provided under a DISCLAIMER OF WARRANTY available from
  4. ; Motorola DSP Operation, 6501 Wm. Cannon Drive W., Austin, Tx., 78735.
  5. ; 
  6. ; Last Update 24 Sep 87   Version 1.1 
  7. ;
  8. ; Sorting by Heapsort method
  9. ;
  10. sort2   macro   ARRAY,N_ITEMS   
  11. sort2   ident   1,1
  12.  
  13. ;
  14. ; reference: Niklaus Writh, "Algorithms + Data Structures = Programs", 
  15. ;            Prentice-Hall, 1976, Program 2.8, page 75
  16. ;
  17. ; ARRAY = location of an array of numbers in X memory space, 
  18. ;         first item is located at ARRAY.
  19. ; N_ITEMS = number of items in the array
  20. ;
  21. ; registers used: r0..r4
  22. ;                 a,b,y1,x0,x1
  23. ;                 assumes m0..m4 = $ffff
  24. ;                 uses 3 words of stack 
  25. ;
  26. ;
  27.         move    #ARRAY-1,b                      ; constant
  28.         move    #>(N_ITEMS/2)+ARRAY,r0          ;r0=l
  29.         move    #>ARRAY+N_ITEMS-1,r1            ;r1=r
  30.         move    r1,y1
  31.  
  32.         do      #N_ITEMS/2,_wend1
  33.         move                    (r0)-
  34.         jsr     _sift          
  35. _wend1
  36.  
  37.  
  38.         do      #N_ITEMS-1,_wend2
  39.         move    x:ARRAY,x1                      ;x1=x
  40.         move    x:(r1),x0
  41.         move    x0,x:ARRAY
  42.         move    x1,x:(r1)- 
  43.         move    r1,y1   
  44.         jsr     _sift
  45. _wend2  jmp     _end
  46.  
  47. ;
  48. ; sift
  49. ; 
  50. _sift   move    r0,r3                           ;"i"=l
  51.         move    x:(r0),x1                       ;x=a("i")
  52. _loop3  move    r3,a                            ;a="i"
  53.         subl    b,a     r3,r2                   ;a = 2*i-array, i="i"=j
  54.         move    a,r3
  55.         cmp     y1,a    r3,r4                   ;j-r
  56.         jgt     _wend3
  57. ;if j<r
  58.         move    x:(r3)+,x0                      ;a(j)
  59.         jeq     _t1                             ;if j<r
  60. ;if a(j)<a(j+1)
  61.         move    x:(r3),a                        ;a(j+1)
  62.         cmp     x0,a                            ;a(j)-a(j+1)
  63. _t1     tle     x0,a    r4,r3
  64.         cmp     x1,a                            ;a(j)-x
  65.         jle     _t13
  66.         move    a,x:(r2)                        ;a(i)=a(j)
  67.         jmp     _loop3
  68. _wend3
  69. _t13    move    x1,x:(r2)                       ;a(i)=x
  70.         rts
  71. _end
  72.         endm
  73.  
  74.  
  75.